//请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: postorder = [4,9,6,5,8]
//输出: false 
//解释：从上图可以看出这不是一颗二叉搜索树
// 
//
// 示例 2： 
//
// 
//
// 
//输入: postorder = [4,6,5,9,8]
//输出: true 
//解释：可构建的二叉搜索树如上图
// 
//
// 
//
// 提示： 
//
// 
// 数组长度 <= 1000 
// postorder 中无重复数字 
// 
//
// 
//
// Related Topics 栈 树 二叉搜索树 递归 数组 二叉树 单调栈 👍 787 👎 0


package LeetCode.editor.cn;

import java.util.Stack;

/**
 * @author ldltd
 * @date 2025-05-08 21:47:31
 * @description LCR 152.验证二叉搜索树的后序遍历序列
 */
public class ErChaSouSuoShuDeHouXuBianLiXuLieLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ErChaSouSuoShuDeHouXuBianLiXuLieLcof fun=new ErChaSouSuoShuDeHouXuBianLiXuLieLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

	 /**
		 bacause the postorder is a binary search tree, so the last element is the root node
	 *	 the left subtree is less than the root node, and the right subtree is greater than the root node
	 */
	// timeComplexity O(n^2)  spaceComplexity O(n)
	public boolean verifyTreeOrder(int[] postorder) {
		return recur(postorder, 0, postorder.length - 1);
	}
	boolean recur(int[] postorder, int i, int j) {
		// node count less than 2, no need to check
		if(i >= j) return true;
		//divide the left and right subtree
		int p = i;
		// find the first element greater than the root node,mark it as m
		// it could be subdivided into left and right subtrees as  (i, m - 1) and (m, j - 1)
		// the root node is postorder[j]
		while(postorder[p] < postorder[j]) p++;
		int m = p;
		// check if the right subtree is greater than the root node
		while(postorder[p] > postorder[j]) p++;
		// if p is not equal to j, it means that the right subtree has elements less than the root node
		// so it is not a binary search tree
		// otherwise ,continue to check the left and right subtrees
		return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
	}

	/**
	 *  the postOrderTraversal is traversed with the sequence of
	 *  the root node, left subtree and right subtree
	 *  which is the same as the mirror of the preOrderTraversal
	 *  that with the sequence of the root node, right subtree and left subtree
	 *  so we can use the Monotonic stack to simulate the preOrderTraversal
	 *	the process is as follows:
 *			1. push the root node with infinite value into the stack
	 *		2.	traverse the postOrderTraversal from back to front
	 *		3. if the current node is greater than the top of the stack, it means that the current node is in the right subtree
	 *		4. if the current node is less than the top of the stack, it means that the current node is in the left subtree
	 *	    5. while the top of the stack is greater than the current node, pop the top of the stack
	 *	        ,otherwise, the right subtree does not finish traversing, continue to push the current node into the stack
 *	        6. if the current node is less than the root node, it means that the current node fit the binary search tree
	 *	    7. after one while loop, the root node is the top of the stack
	 *
	 * */
	public boolean verifyTreeOrder1(int[] postorder) {
		Stack<Integer> stack = new Stack<>();
		int root = Integer.MAX_VALUE;
		for(int i = postorder.length - 1; i >= 0; i--) {
			// atfter the while loop, the root node is the top of the stack
			// if the left subtree is greater than the root node, it is not a binary search tree
			if(postorder[i] > root) return false;
			// push the root node and the right subtree into the stack
			// if the current node is less than the root node, it is in the left subtree
			// pop all the elements in the stack that are greater than the current node
			// to find the satisfied root node
			while(!stack.isEmpty() && stack.peek() > postorder[i])
				root = stack.pop();
			// push the current node into the stack as the new while loop start point
			stack.add(postorder[i]);
		}
		return true;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
